\section{字串变换(P1032)}
\subsection{题目描述}
已知有两个字串 A, B 及一组字串变换的规则（至多6个规则）:
\begin{compactitem}
\item $A1 -> B1$
\item $A2 -> B2$
\end{compactitem}

规则的含义为：在 A中的子串 A1 可以变换为 B1、A2 可以变换为 B2 …。

例如：A＝'abcd' B＝'xyz'

变换规则为：

$abc->xu\quad ud->y\quad y->yz$

则此时，A 可以经过一系列的变换变为 B，其变换的过程为：

$abcd->xud->xy->xyz$

共进行了三次变换，使得 A 变换为B。


\subsection{输入输出格式}

\textbf{输入格式：}\\
A B \\
A1 B1  \\
A2 B2  $|->$ 变换规则

... ... /

所有字符串长度的上限为 20。

\textbf{输出格式：}\\
若在 10 步（包含 10步）以内能将 A 变换为 B ，则输出最少的变换步数；否则输出"NO ANSWER!"

\subsection{输入输出样例}
\textbf{输入\#1}
\begin{lstlisting}
abcd xyz
abc xu
ud y
y yz
\end{lstlisting}
\textbf{输出\#1}
\begin{lstlisting}
3
\end{lstlisting}
\subsection{分析}
分析
\subsection{代码}
\begin{lstlisting}
#include <stdio.h> 
#include <assert.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <string>
#include <map>
#include <queue>

using namespace std; 

#define SN 21
#define RN 6

struct pair_s {
	char org[SN]; 
	char tgt[SN]; 
}; 

struct bfs_node_s {
	char str[SN]; 
	int  steps; 
}; 

struct pair_s ab; 
struct pair_s rules[RN]; 
int nr_rules; 

queue<struct bfs_node_s *> bfs_q; 
map<string, int> bfs_map; 

void trans(const struct pair_s *rule, const char *org, 
	const char *loc, char *res)
{
	char *d=res; 
	const char *s1, *s2; 
	for(s1=org; s1!=loc; s1++, d++) {
		*d = *s1; 
	}
	for (s2=rule->org; *s2; s2++) {
		s1++; 
	}
	for (s2=rule->tgt; *s2; s2++, d++) {
		*d = *s2; 
	}
	for (;*s1; s1++, d++) {
		*d = *s1; 
	}
	*d = '\0'; 
}

int bfs(void)
{
	struct bfs_node_s *node, *nn; 
	int i, ret; 
	char *p, *loc; 
	if (!strcmp(ab.org, ab.tgt))
		return 0; 
	node = (struct bfs_node_s *)malloc(sizeof(struct bfs_node_s)); 
	assert(node); 
	strcpy(node->str, ab.org); 
	node->steps = 0; 
	bfs_q.push(node); 
	while(!bfs_q.empty()) {
		node = bfs_q.front(); 
		bfs_q.pop(); 
		for (i=0; i<nr_rules; i++) {
			p = node->str; 
			while(*p) {
				p = strstr(p, rules[i].org); 
				if (!p) {
					break; 
				}
				loc = p;
				p++; 
				nn = (struct bfs_node_s *)malloc(sizeof(struct bfs_node_s)); 
				assert(nn); 
				nn->steps = node->steps + 1; 
				trans(&rules[i], node->str, loc, nn->str); 
				if (!strcmp(nn->str, ab.tgt)) {
					ret = nn->steps; 
					free(nn); 
					return ret; 
				} else if (nn->steps>=10) {
					free(nn); 
				} else if(bfs_map.count(nn->str)==1) {
					free(nn); 
				} else {
					bfs_map[nn->str] = 1; 
					bfs_q.push(nn); 
				}
			}
		}
		free(node); 
	}
	return -1; 
}

int main()
{
	int ret; 
	cin>>ab.org>>ab.tgt; 
	while(cin>>rules[nr_rules].org>>rules[nr_rules].tgt) {
		nr_rules ++; 
	}
	ret = bfs(); 
	if (ret>=0) 
		printf("%d\n", ret); 
	else 
		printf("NO ANSWER!\n"); 
	return 0; 
}
\end{lstlisting}
